package com.ycz.algorithm.utils.heap.myheap;

import java.util.*;

/**
 * @author yancz
 * @ClassName MyMaxHeap
 * @description: 大顶堆自定义实现
 * @date 2025-01-08 11:17:03
 * @version: 1.0
 */
public class MyMaxHeap {

    private static List<Integer> maxHeap = new ArrayList<>();

    // 获取堆大小
    int size() {
        return maxHeap.size();
    }

    // 判断堆是否为空
    boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    /*
     * @author yancz
     * @description 获取左子节点索引
     * @date 2025/1/8 11:18
     * @param i 当前节点索引
     * @return int
     */
    int getLeftIndex(int i) {
        return 2 * i + 1;
    }

    // 获取右子节点索引
    int getRightIndex(int i) {
        return 2 * i + 2;
    }

    // 获取父节点索引，向下取整
    int getParentIndex(int i) {
        return (i - 1) / 2;
    }

    // 访问堆顶元素即访问根元素，也就是列表的第一个元素
    int peek() {
        return maxHeap.get(0);
    }

    // 元素入堆
    void push(int val) {
        maxHeap.add(val);
        siftUp(size() - 1);
    }

    /*
     * @author yancz
     * @description // 从堆底到堆顶开始堆化
     * @date 2025/1/8 11:33
     * @param i 节点索引
     * @return void
     */
    private void siftUp(int i) {
        while (true) {
            // 获取父节点索引
            int parentIndex = getParentIndex(i);
            if (parentIndex < 0 || maxHeap.get(i) <= maxHeap.get(parentIndex)) { // 当越过根节点或根节点无须修复时退出
                break;
            }
            // 若节点值>父节点值，则交换位置
            swap(i, parentIndex);
            i = parentIndex; // 继续循环向上进行堆化
        }
    }

    // 元素出堆
    int pop() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("堆为空！");
        }
        swap(0, size() - 1); // 交换堆顶元素和最后一个元素
        // 删除最后一个元素
        int val = maxHeap.remove(size() - 1);
        siftDown(0);
        return val;
    }

    /*
     * @author yancz
     * @description // 从堆顶到堆底开始堆化
     * @date 2025/1/8 11:52
     * @param i 节点索引
     * @return void
     */
    private void siftDown(int i) {
        while (true) {
            // 判断i,left,right中最大的节点，索引记为max
            int left = getLeftIndex(i); // 左节点索引
            int right = getRightIndex(i); // 右节点索引
            int max = i; // 最大节点索引
            if (left < size() && maxHeap.get(left) > maxHeap.get(max)) {
                max = left;
            }
            if (right < size() && maxHeap.get(right) > maxHeap.get(max)) {
                max = right;
            }
            if (max == i) { // 当max值不变时退出
                break;
            }
            swap(i, max);
            i = max; // 继续循环向下进行堆化
        }
    }

    // 交换列表中两个位置的元素
    private void swap(int i, int j) {
        int temp = maxHeap.get(i);
        maxHeap.set(i, maxHeap.get(j));
        maxHeap.set(j, temp);
    }

    /*
     * @author yancz
     * @description // 构建大顶堆
     * @date 2025/1/8 15:59
     * @param list
     * @return void
     */
    void buildMaxHeap(List<Integer> list) {
        maxHeap = new ArrayList<>(list);
        int lastIndex = getParentIndex(size() - 1); // 最后一个非叶子节点索引开始，自底向上堆化
        for (int i = lastIndex; i >= 0; i--) {
            siftDown(i);
        }
    }

    /*
     * @author yancz
     * @description // topK问题，从n个元素中取出前k个最大的元素
     * @date 2025/1/8 16:41
     * @param nums 原数组
     * @param k 数量
     * @return Queue<Integer>
     */
    Queue<Integer> topKHeap(int[] nums, int k) {
        // 先初始化一个小顶堆
        Queue<Integer> queue = new PriorityQueue<>();
        // 然后将数组的前k个元素入堆
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        // 从第k+1个元素开始，与堆顶元素比较，若比堆顶元素小，则替换堆顶元素，并重新调整堆，保持堆的大小为k
        for (int i = k; i < nums.length; i++) {
            //若当前元素大于堆顶元素，则堆顶元素出堆，当前元素入堆
            if (nums[i] > queue.peek()) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }
        return queue;
    }

    // 打印堆中元素
    void commonPrint() {
        for (int i : maxHeap) {
            System.out.print(i + "\t");
        }
        System.out.println();
        System.out.println("堆顶元素：" + peek());
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        MyMaxHeap myMaxHeap = new MyMaxHeap();
        myMaxHeap.push(1);
        myMaxHeap.push(3);
        myMaxHeap.push(2);
        myMaxHeap.push(5);
        myMaxHeap.push(4);
        myMaxHeap.commonPrint();
        int val = myMaxHeap.pop();
        System.out.println("出堆元素：" + val);
        myMaxHeap.commonPrint();
        System.out.println("-----------------------------");
        maxHeap = new ArrayList<>(Arrays.asList(1, 3, 2, 5, 4));
        System.out.println("构建堆之前：");
        for (int i : maxHeap) {
            System.out.print(i + "\t");
        }
        System.out.println();
        // 构建大顶堆
        myMaxHeap.buildMaxHeap(maxHeap);
        System.out.println("构建堆之后：");
        for (int i : maxHeap) {
            System.out.print(i + "\t");
        }
        System.out.println();
        // 测试topK问题
        int[] nums = {4, 5, 1, 6, 2, 7, 3, 8};
        Queue<Integer> heap = myMaxHeap.topKHeap(nums, 4);
        System.out.println("前4个最大元素：");
        for (int i : heap) {
            System.out.print(i + "\t");
        }
    }

}
